package com.leetcode.二分查找;

import javax.xml.stream.events.StartDocument;

//搜索二维矩阵
public class lc_74 {
    public static void main(String[] args) {
        int[][] matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,50}};
        System.out.println(searchMatrix(matrix, 11));
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        //思路: 先判断可能在哪一行: 大于等于matrix[i][0] 小于matrix[i+1][0]
        int index = 0;
        int m = matrix.length - 1;
        int n = matrix[0].length - 1;
        //大于最大值直接返回false;
        if(target > matrix[m][n]){
            return false;
        }
        //找到在index行
        for(int i = 0; i < matrix.length; i++){
            if(target >= matrix[i][0] && target <= matrix[i][n]){
                index = i;
                break;
            }
        }

        //使用二分查找法查找第一个 >= target的元素下标
        int left = -1;
        int right = matrix[0].length;
        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            if(target <= matrix[index][mid]){
                right = mid;
            } else{
                left = mid;
            }
        }
        return right != matrix[0].length && matrix[index][right] == target;
    }
}
